//
//  BBDistortionMesh.m
//  BBTouch
//
//  Created by ben smith on 8/12/08.
//  This file is part of BBTouch.
//
//  BBTouch is free software: you can redistribute it and/or modify
//  it under the terms of the GNU Lesser General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.

//  BBTouch is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU Lesser General Public License for more details.

//  You should have received a copy of the GNU Lesser General Public License
//  along with BBTouch.  If not, see <http://www.gnu.org/licenses/>.
// 
//  Copyright 2008 Ben Britten Smith ben@benbritten.com .
//

#import "BBDistortionMesh.h"
#import "BBIndexedVertex.h"

// mesh

@implementation BBDistortionMesh

@synthesize height;
@synthesize width;
@synthesize vertices;
@synthesize boundingRect;


// standard init with coder kinda method
- (id)initWithCoder:(NSCoder *)coder
{
	if (![self init]) return nil;
	self.height = [coder decodeIntegerForKey:@"height"];
	self.width = [coder decodeIntegerForKey:@"width"];
	self.vertices = [coder decodeObjectForKey:@"vertices"];
	// be sure to calc the bounding rect
	[self calculateBoundingRect];
	return self;
}

// encode myself
- (void)encodeWithCoder:(NSCoder *)coder
{
	[coder encodeInteger:width forKey:@"width"];
	[coder encodeInteger:height forKey:@"height"];
	[coder encodeObject:vertices forKey:@"vertices"];
	return;	
}

// generates a dictionary of our current values
// this is like encodeWithCoder, but I am using dictionaries instead of
// encoders because I want an XML file at the end of it
-(NSDictionary*)propertyDictionary
{
	// make a new dict for all my stuff
	NSMutableDictionary * props = [NSMutableDictionary dictionary];
	// add in the easy variables
	[props setObject:[NSNumber numberWithInteger:height] forKey:@"height"];
	[props setObject:[NSNumber numberWithInteger:width] forKey:@"width"];
	
	// now build an array for my vertices
	NSMutableArray * vertProps = [NSMutableArray array];
	for (BBIndexedVertex * vert in vertices) {
		[vertProps addObject:[vert propertyDictionary]];
	}
	[props setObject:vertProps forKey:@"vertices"];
	
	return props;
}


// just a handy way of making new filled in meshes
+(BBDistortionMesh*)meshWithHeight:(NSInteger)h width:(NSInteger)w boundingRectangle:(NSRect)boundingRectangle
{
	BBDistortionMesh * newMesh = [[BBDistortionMesh alloc] init];
	newMesh.height = h;
	newMesh.width = w;
	
	// this will build a new mesh with the specified heights and width and lay it into a bounding rectangle evenly	
	// grab the bounds frame, use that for my initial positions
	
	// set up my increments (ie how far apart each vertex is)
	float xincrement = boundingRectangle.size.width/(w - 1);
	float yincrement = boundingRectangle.size.height/(h - 1);
	float xcurrent = NSMinX(boundingRectangle);
	float ycurrent = NSMinY(boundingRectangle);
	
	int ix,iy;
	for (ix = 0 ; ix < w; ix++) {
		ycurrent = NSMinY(boundingRectangle);
		for (iy = 0 ; iy < h; iy++) {
			// now set the specific layer position
			[newMesh addVertexAtPoint:NSMakePoint(xcurrent, ycurrent)];
			ycurrent += yincrement;
		}
		xcurrent += xincrement;
	}		
	// all done
	return [newMesh autorelease];
}

- (id) init
{
	self = [super init];
	if (self != nil) {
		vertices = [[NSMutableArray alloc] init];
		self.height = 5; // some nice defaults
		self.width = 6;
		self.boundingRect = NSZeroRect;
	}
	return self;
}

- (void) dealloc
{
	[vertices removeObserver:self fromObjectsAtIndexes:[NSIndexSet indexSetWithIndexesInRange:NSMakeRange(0, [vertices count])]  forKeyPath:@"point"];
	[vertices release];
	[super dealloc];
}

-(NSRect)boundingRect
{
	if (NSEqualRects(boundingRect, NSZeroRect)) [self calculateBoundingRect];
	return boundingRect;
}

-(void)calculateBoundingRect
{
	[self willChangeValueForKey:@"boundingRect"];
	if ([vertices count] == 0) {
		boundingRect = NSZeroRect;
		[self didChangeValueForKey:@"boundingRect"];
		return;
	}
	// quick and dirty: find the min/max in x and y
	NSInteger maxX,maxY,minX,minY;
	NSPoint thisPoint = [[vertices objectAtIndex:0] point];
	maxX = minX = thisPoint.x;
	maxY = minY = thisPoint.y;
	NSInteger index;
	for (index = 1; index < [vertices count]; index++) {
		thisPoint = [[vertices objectAtIndex:index] point];
		if (maxX < thisPoint.x) maxX = thisPoint.x;
		if (maxY < thisPoint.y) maxY = thisPoint.y;
		if (minX > thisPoint.x) minX = thisPoint.x;
		if (minY > thisPoint.y) minY = thisPoint.y;
	}
	if ((maxX == minX) || (maxY == minY)) {
		boundingRect = NSZeroRect;
		[self didChangeValueForKey:@"boundingRect"];
		return;		
	}
	boundingRect = NSMakeRect(minX, minY, maxX - minX, maxY - minY);
	[self didChangeValueForKey:@"boundingRect"];
}

-(void)addVertexAtPoint:(NSPoint)p
{
	BBIndexedVertex * newVert = [BBIndexedVertex vertextWithIndex:[vertices count] point:p];
	[vertices addObject:newVert];
	[newVert addObserver:self forKeyPath:@"point" options:NSKeyValueObservingOptionNew context:nil];
}

- (void)observeValueForKeyPath:(NSString *)keyPath ofObject:(id)object change:(NSDictionary *)change context:(void *)context
{
	[self calculateBoundingRect];
}

// returns the vertices that bound the supplied point
-(NSArray*)boundingTriangleForPoint:(NSPoint)p;
{
	// need to iterate through all the triangles formed by our
	// mesh and find the one that contains this point
	// for any given vertex, there are 4 quads that it is a part of
	// so for any given vertex, there are 8 triangles to check
	// however, this is a bounded graph, so if we start on
	// the left then we will only need to check 4 triangles on the right per
	// vertex because the ones on the left will have been checked already

	
	int ix,iy;
	for (ix = 0 ; ix < width; ix++) {
		for (iy = 0 ; iy < height; iy++) {
			int vertIndex = ix * height + iy;
			BBIndexedVertex* thisVertex = [vertices objectAtIndex:vertIndex];
			// find the 4 triangles
			// one up and one over
			// one over and one up
			// one over and one down
			// one down and one over
			
			// first setup my locals
			BBIndexedVertex* oneUp = nil;
			BBIndexedVertex* oneOver = nil;
			BBIndexedVertex* oneDown = nil;
			BBIndexedVertex* oneUpOneOver = nil;
			BBIndexedVertex* oneDownOneOver = nil;
			
			// check my bounds and assign the locals accordingly
			if (vertIndex + height < [vertices count]) {
				oneOver = [vertices objectAtIndex:vertIndex + height];
			}
			if ((vertIndex + 1 < [vertices count]) && (iy != height - 1)) {
				oneUp = [vertices objectAtIndex:vertIndex + 1];				
			}
			if ((vertIndex + height + 1 < [vertices count]) && (iy != height - 1)) {
				oneUpOneOver = [vertices objectAtIndex:vertIndex + height + 1];				
			}
			if ((vertIndex - 1 >= 0) && (iy != 0)) {
				oneDown = [vertices objectAtIndex:vertIndex - 1];
			}
			if ((vertIndex + height - 1 < [vertices count]) && (iy != 0)) {
				oneDownOneOver = [vertices objectAtIndex:vertIndex + height - 1];				
			}
			
			// now, check each triangle if it is inside the mesh 
			// (ie) the layers are not nil
			// if we get a hit return straight away
			if (((oneUp != nil) && (oneUpOneOver != nil)) &&
					([self point:p inTriangleA:thisVertex.point b:oneUp.point c:oneUpOneOver.point])) 
				return [NSArray arrayWithObjects:thisVertex,oneUp,oneUpOneOver,nil];

			if (((oneOver != nil) && (oneUpOneOver != nil)) &&
					([self point:p inTriangleA:thisVertex.point b:oneOver.point c:oneUpOneOver.point]))
				return [NSArray arrayWithObjects:thisVertex,oneOver,oneUpOneOver,nil];

			if (((oneOver != nil) && (oneDown != nil)) &&
					([self point:p inTriangleA:thisVertex.point b:oneOver.point c:oneDown.point]))
				return [NSArray arrayWithObjects:thisVertex,oneOver,oneDown,nil];

			if (((oneDownOneOver != nil) && (oneDown != nil)) &&
				([self point:p inTriangleA:thisVertex.point b:oneDownOneOver.point c:oneDown.point]))
				return [NSArray arrayWithObjects:thisVertex,oneDownOneOver,oneDown,nil];
		}
	}		
	// point is not in the mesh, return nil
	return nil;
}


-(BOOL)point:(NSPoint)p inTriangleA:(NSPoint)a b:(NSPoint)b c:(NSPoint)c
{
	// using barycentric math, calculate the U,V coords and see if
	// this point is inside the triangle
	// good explanation found here:
	// http://www.blackpawn.com/texts/pointinpoly/default.html
	
	// Compute vectors relative to a       
	NSPoint v0 = NSMakePoint(c.x - a.x, c.y - a.y);
	NSPoint v1 = NSMakePoint(b.x - a.x, b.y - a.y);
	NSPoint v2 = NSMakePoint(p.x - a.x, p.y - a.y);
	
	// Compute dot products
	float dot00 = [self dotA:v0 b:v0];
	float dot01 = [self dotA:v0 b:v1];
	float dot02 = [self dotA:v0 b:v2];
	float dot11 = [self dotA:v1 b:v1];
	float dot12 = [self dotA:v1 b:v2];
	
	// Compute barycentric coordinates
	float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
	float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
	float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
	
	// Check if point is in triangle
	return ((u > 0) && (v > 0) && (u + v < 1));
}

// the dot product
-(float)dotA:(NSPoint)a b:(NSPoint)b
{
	return (a.x * b.x) + (a.y * b.y);
}

// just a nicer way to call this method
-(NSPoint)destinationPointFromSourcePoint:(NSPoint)srcP
														sourceVertices:(NSArray*)verts
{
	return [self destinationPointFromSourcePoint:srcP 
																 sourceVertexA:[verts objectAtIndex:0] 
																 sourceVertexB:[verts objectAtIndex:1] 
																 sourceVertexC:[verts objectAtIndex:2]];
}	


// this is the big distortion calculation
// it takes the 4 known points from the source mesh
// and 3 known points from the destination mesh
// and finds the wanted point in the destination
-(NSPoint)destinationPointFromSourcePoint:(NSPoint)srcP
										 sourceVertexA:(BBIndexedVertex*)sa
										 sourceVertexB:(BBIndexedVertex*)sb
										 sourceVertexC:(BBIndexedVertex*)sc
{
	// this algorithm is inspired by the CTouchScreen::cameraToScreenSpace
	// method in touchlib
	//  it is a standard barycentric position calc using the 
	// ration of the areas of the inner triangles formed by the 
	// three vertices and the hit point
	float areaT = [self areaOfTriangleWithPoints:sa.point b:sb.point c:sc.point]; // total area of source
	
	// area1 is the area of the triangle opposite the A vertex, or the area between 2,3,4 and so on
	// find the source area and normalize them
	float area1 = [self areaOfTriangleWithPoints:sb.point b:sc.point c:srcP]/areaT;
	float area2 = [self areaOfTriangleWithPoints:sa.point b:sc.point c:srcP]/areaT;
	float area3 = [self areaOfTriangleWithPoints:sb.point b:sa.point c:srcP]/areaT;
	
	
	// nearly ready to 'do the math', but first, load up some convenience locals
	// with the 'destination' vertices
	BBIndexedVertex* da = [vertices objectAtIndex:sa.index];
	BBIndexedVertex* db = [vertices objectAtIndex:sb.index];
	BBIndexedVertex* dc = [vertices objectAtIndex:sc.index];
	
	// now using the normalized areas, we can 'walk' the three vectors to
	// get the wanted point in the destination mesh
	
	NSPoint p1 = NSMakePoint(da.point.x * area1, da.point.y * area1);
	NSPoint p2 = NSMakePoint(db.point.x * area2, db.point.y * area2);
	NSPoint p3 = NSMakePoint(dc.point.x * area3, dc.point.y * area3);
	
	return NSMakePoint(p1.x + p2.x + p3.x, p1.y + p2.y + p3.y);
}

-(float)areaOfTriangleWithPoints:(NSPoint)p1 b:(NSPoint)p2 c:(NSPoint)p3
{
	// got this area calculation from
	// http://www.btinternet.com/~se16/hgb/triangle.htm
	
	// the points need to be clockwise for this to work properly
	// instead of requiring that they come in the proper order
	// we will just make sure here
	
	// make the higest point the start
	NSPoint A,B,C;
	A = p1;
	if (p2.y > A.y) A = p2;
	if (p3.y > A.y) A = p3;
	
	// now find the next point that is 'on the right', ie clockwise from A
	// if A is p1, then check the other 2
	if (NSEqualPoints(A, p1)) {
		if (p2.x > p3.x) {
			B = p2;
			C = p3;
		} else {
			B = p3;
			C = p2;
		}
	}
	
	// if A is p2 then .. you get the idea
	if (NSEqualPoints(A, p2)) {
		if (p1.x > p3.x) {
			B = p1;
			C = p3;
		} else {
			B = p3;
			C = p1;
		}
	}
	
	// if A is p3 yadda yadda
	if (NSEqualPoints(A, p3)) {
		if (p1.x > p2.x) {
			B = p1;
			C = p2;
		} else {
			B = p2;
			C = p1;
		}
	}
	 
	// do the area calculation
	// what we are basically doing, tho it is not very obvious is
	// we are taking the area of the bounding rectangle and 
	// subtracting the outer right triangles which are easy
	// to find instead of trying to make two right triangles inside the
	// source triangle. if that makes no sense, see the link above
	float f = A.x - B.x;
	float g = A.y - C.y;
	float w = A.y - B.y;
	float v = A.x - C.x;
	return fabs(((f * g)/2.0) - ((v * w)/2.0));
}

-(void)scaleBoundingRectToNewRect:(NSRect)newRect
{
	// there is probably a nice matrix to do this, but i dont have that in front of me
	// sooo... i will do it the hard way
	
	// find the scaling vector
	// apply that to all the vertices
	float scaleX = NSWidth(newRect)/(NSWidth([self boundingRect]));
	float scaleY = NSHeight(newRect)/(NSHeight([self boundingRect]));

	// i think i need to offset to zero here
	// probably cant hurt
	
	NSPoint sourceOrigin = [self boundingRect].origin;
	NSPoint destOrigin = newRect.origin;
	
	for (BBIndexedVertex * vert in vertices) {
		NSPoint p = [vert point];
		p.x -= sourceOrigin.x;
		p.y -= sourceOrigin.y;
		
		p.x *= scaleX;
		p.y *= scaleY;
		
		p.x += destOrigin.x;
		p.y += destOrigin.y;
		
		[vert setPoint:p];
	}
	[self calculateBoundingRect];
}

// rotates all the points about the center of the mesh by 'degrees'
-(void)rotateMeshInRadians:(float)theta
{
	// i totally know that you can do this with a matrix. but i dont know that method off
	// the top of my head, whereas i do remember high scholl trig, so there you go

	NSPoint center = NSMakePoint(NSMidX([self boundingRect]), NSMidY([self boundingRect]));
	
	for (BBIndexedVertex * vert in vertices) {
		NSPoint meshPoint = [vert point];
		meshPoint.x = (cos(theta) * (meshPoint.x - center.x)) - (sin(theta) * (meshPoint.y - center.y)) + center.x;
		meshPoint.y = (sin(theta) * (meshPoint.x - center.x)) + (cos(theta) * (meshPoint.y - center.y)) + center.y;
		[vert setPoint:meshPoint];
	}
	[self calculateBoundingRect];
	
}

// yet another transformative method
// simple: just take the points and flip them on the y axis
// first offset to 0
// then flip based on the height
// then re-offset back to where they will reside
// there is probably a better way to do this
-(void)flipMeshVertically
{
	NSPoint sourceOrigin = [self boundingRect].origin;
	float h = NSHeight([self boundingRect]);
	for (BBIndexedVertex * vert in vertices) {
		NSPoint meshPoint = [vert point];
		meshPoint.y -= sourceOrigin.y;
		meshPoint.y = h - meshPoint.y;
		meshPoint.y += sourceOrigin.y;
		[vert setPoint:meshPoint];
	}	
	[self calculateBoundingRect];
}

// yet another transformative method
// same as the vert, but with X
-(void)flipMeshHorizontally
{
	NSPoint sourceOrigin = [self boundingRect].origin;
	float w = NSWidth([self boundingRect]);
	for (BBIndexedVertex * vert in vertices) {
		NSPoint meshPoint = [vert point];
		meshPoint.x -= sourceOrigin.x;
		meshPoint.x = w - meshPoint.x;
		meshPoint.x += sourceOrigin.x;
		[vert setPoint:meshPoint];
	}	
	[self calculateBoundingRect];
}


@end
